Practice | GeeksforGeeks | A computer science portal for geeks
LIVE   BATCHES
Quiz

This track of the course covers the topic "Heap".

In details, this track will cover:

  • Basics: Introduction to Heap.
  • Operations: Creation, Insertion, Deletion, Heapify.
  • Implementation: How to implement Heaps and priority queues in CPP and Java.
  • Types: How Min Heap and Max Heap are different.

Objective: The objective of this track is to familiarize the learners with Heaps.

Track Content:

  • 2 Video Lecture on Heap.
  • Theoretical Articles.
  • Programming practice problems.
  • 10 Quiz questions for practice.

Assessment: All Tracks in every week are associated with weekly contests.

We have combined Classroom and Theory tab and created a new Learn tab for easy access. You can access Classroom and Theory from the left panel.

This video provides an introductory lecture to Binary Heap.


This video discusses the implementation of a Binary Heap.
Codes:


This video implements the insertion method of Binary Heap.
Codes:


This video discusses the Heapify and Extract operation and how can it be implemented in a Binary Heap.
Codes:


This video discusses the Decrease Key, Delete and Build Heap operation of Binary Heap.
Codes:


This video discusses the working and implementation of the Priority Queue in C++. It also discusses the various general applications of Priority Queue.
Codes:


This video explains the implementation of the Priority Queue in Java.

Codes:


This video discusses the problem of how to Sort an array that is already k-sorted.
Codes:


This video discusses the problem of buying the maximum items with a given sum.
Codes:


This video discusses the problem of calculating the K Largest Elements in an unsorted array
Codes:


This video discusses the calculation of a Median of a Stream.
Codes:

A Heap is a Tree-based data structure, which satisfies the below properties:
  1. A Heap is a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible).

  2. A Heap is either Min Heap or Max Heap. In a Min-Heap, the key at root must be minimum among all keys present in the Binary Heap. The same property must be recursively true for all nodes in the Tree. Max Heap is similar to MinHeap.

Binary Heap: A Binary Heap is a heap where each node can have at most two children. In other words, a Binary Heap is a complete Binary Tree satisfying the above-mentioned properties.



Representing Binary Heaps

Since a Binary Heap is a complete Binary Tree, it can be easily represented using Arrays.
  • The root element will be at Arr[0].
  • Below table shows indexes of other nodes for the ith node, i.e., Arr[i]:
    Arr[(i-1)/2] Returns the parent node
    Arr[(2*i)+1] Returns the left child node
    Arr[(2*i)+2] Returns the right child node

Getting Maximum Element: In a Max-Heap, the maximum element is always present at the root node which is the first element in the array used to represent the Heap. So, the maximum element from a max heap can be simply obtained by returning the root node as Arr[0] in O(1) time complexity.

Getting Minimum Element: In a Min-Heap, the minimum element is always present at the root node which is the first element in the array used to represent the Heap. So, the minimum element from a minheap can be simply obtained by returning the root node as Arr[0] in O(1) time complexity.

Heapifying an Element

Generally, on inserting a new element onto a Heap, it does not satisfy the property of Heap as stated above on its own. The process of placing the element at the correct location so that it satisfies the Heap property is known as Heapify.

Heapifying in a Max Heap: The property of Max Heap says that every node's value must be greater than the values of its children nodes. So, to heapify a particular node swap the value of the node with the maximum value of its children nodes and continue the process until all of the nodes below it satisfies the Heap property.

Consider the below heap as a Max-Heap:


In the above heap, node 4 does not follow the Heap property. Let's heapify the root node, node 4.
  • Step 1: Swap the node 4 with the maximum of its childrens i.e., max(10, 3).

  • Step 2: Again the node 4 does not follow the heap property. Swap the node 4 with the maximum of its new childrens i.e., max(5, 1).

  • The Node 4 is now heapified successfully and placed at it's correct position.

Time Complexity: The time complexity to heapify a single node is O(h), where h is equal to log(N) in a complete binary tree where N is the total number of nodes.

Deletion in Heap


Given a Binary Heap and an element present in the given Heap. The task is to delete an element from this Heap.

The standard deletion operation on Heap is to delete the element present at the root node of the Heap. That is if it is a Max Heap, the standard deletion operation will delete the maximum element and if it is a Min heap, it will delete the minimum element.

Process of Root Deletion (Or Extract Min in Min Heap):
Since deleting an element at any intermediary position in the heap can be costly, so we can simply replace the element to be deleted by the last element and delete the last element of the Heap.
  • Replace the root or element to be deleted by the last element.
  • Delete the last element from the Heap.
  • Since, the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore, heapify the last node placed at the position of root.

Illustration:
Suppose the Heap is a Max-Heap as:


The element to be deleted is root, i.e. 10.

Process:
The last element is 4.

Step 1: Replace the last element with root, and delete it.


Step 2: Heapify root.
Final Heap:


Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:
5 4 3 2

How to Delete Nnn-Root elements?:
Below are the steps to delete an element at given index from Min Heap
  • Replace the element to be deleted with minus Infinite (INT_MIN in C++ and Integer.MIN_VALUE in Java)
  • Keep swapping the minus infinite value with parent until it reaches root
  • Now delete the root using process discussed above
Illustration
Let us try deleting 30 from below Min Heap


We replace 30 with -INF


We move -INF to root by swapping with parent
nodes one by one


Now Delete Root (We first replace it with last node
then call heapify)





Insertion in Heaps

The insertion operation is also similar to that of the deletion process.
Given a Binary Heap and a new element to be added to this Heap. The task is to insert the new element to the Heap maintaining the properties of Heap.

Process of Insertion: Elements can be isnerted to the heap following a similar approach as discussed above for deletion. The idea is to:
  • First increase the heap size by 1, so that it can store the new element.
  • Insert the new element at the end of the Heap.
  • This newly inserted element may distort the properties of Heap for its parents. So, in order to keep the properties of Heap, heapify this newly inserted element following a bottom-up approach.

Illustration:
Suppose the Heap is a Max-Heap as:


The new element to be inserted is 15.

Process:
Step 1: Insert the new element at the end.


Step 2: Heapify the new element following bottom-up
approach.
-> 15 is less than its parent 3, swap them.


-> 15 is again less than its parent 10, swap them.


Therefore, the final heap after insertion is:
-> 15 is less than its parent 3, swap them.


Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:
15 5 10 2 4 3
Given N elements. The task is to build a Binary Heap from the given array. The heap can be either Max Heap or Min Heap.

Suppose the given input elements are: 4, 10, 3, 5, 1.

The corresponding complete binary tree for this array of elements [4, 10, 3, 5, 1] will be:


Root is at index 0 in array.
Left child of i-th node is at (2*i + 1)th index.
Left child of i-th node is at (2*i + 2)th index.
Parent of i-th node is at (i-1)/2 index.

Suppose, we need to build a Max-Heap from the above-given array elements. It can be clearly seen that the above complete binary tree formed does not follow the Heap property. So, the idea is to heapify the complete binary tree formed from the array in reverse level order following top-down approach.

That is first heapify, the last node in level order traversal of the tree, then heapify the second last node and so on.


Time Complexity: Heapify a single node takes O(Log N) time complexity where N is the total number of Nodes. Therefore, building the entire Heap will take N heapify operations and the total time complexity will be O(N*logN).

Optimized Approach: The above approach can be optimized by observing the fact that the leaf nodes need not to be heapified as they already follow the heap property. Also, the array representation of the complete binary tree contains the level order traversal of the tree.

So the idea is to find the position of the last non-leaf node and perform the heapify operation of each non-leaf node in reverse level order.
Last non-leaf node = parent of last-node.
or, Last non-leaf node = parent of node at (n-1)th index.
or, Last non-leaf node = Node at index ((n-1) - 1)/2.
= (n - 2)/2.

Illustration:
Array = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}

Corresponding Complete Binary Tree is:


The task to build a Max-Heap from above array.

Total Nodes = 11.
Last Non-leaf node index = (11/2) - 1 = 4.
Therefore, last non-leaf node = 6.

To build the heap, heapify only the nodes:
[1, 3, 5, 4, 6] in reverse order.

Heapify 6: Swap 6 and 17.


Heapify 4: Swap 4 and 9.


Heapify 5: Swap 13 and 5.


Heapify 3: First Swap 3 and 17, again swap 3 and 15.


Heapify 1: First Swap 1 and 17, again swap 1 and 15,
finally swap 1 and 6.


Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:
Array representation of Heap is:
17 15 13 9 6 5 10 4 8 3 1

Heaps in C++

In C++ the priority_queue container can be used to implement Heaps. The priority_queue in C++ is a built-in container class which is used to implement priority queues easily. This container uses max heap internally to implement a priority queue efficiently. Therefore, it can be also used in-place of max heaps.

This container can also be modified by passing some additional parameters to be used as a Min Heap.

Syntax:
  • For implementing Max Heap:
    priority_queue< type_of_data > name_of_heap;
  • For implementing Min Heap:
    priority_queue< type, vector<type>, greater<type> > name_of_heap;

Methods of priority queue:
  • priority_queue::empty(): The empty() function returns whether the queue is empty.
  • priority_queue::size(): The size() function returns the size of the queue.
  • priority_queue::top(): This function returns a reference to the top most element of the queue.
  • priority_queue::push(): The push(g) function adds the element ‘g’ at the end of the queue.
  • priority_queue::pop(): The pop() function deletes the first element of the queue.
  • priority_queue::swap(): This function is used to swap the contents of one priority queue with another priority queue of same type and size.

Note: The above functions are applicable in case of both Max-Heap and Min-heap implementation of priority_queue container.

Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:
Element at top of Max Heap at every step:
30 20 10 5 1

Element at top of Min Heap at every step:
1 5 10 20 30


Heaps in Java

Java also provides us with a built-in class named PriorityQueue which can be used to implement both Max heap and Min heap easily and efficiently.

By default, the PriorityQueue class implements a Min-Heap. However, it can also be modified by using a comparator function to implement Max-Heap as well as shown in the below syntax.

Syntax:
  • Implementing Max Heap:
    Queue<Integer> max_heap = new PriorityQueue<>(                         
    Collections.reverseOrder());
  • Implementing Min Heap:
    Queue<Integer> min_heap = new PriorityQueue<>(); 

Some useful method of PriorityQueue class in Java:
  • boolean add(E element): This method inserts the specified element into this priority queue.
  • public remove(): This method removes a single instance of the specified element from this queue, if it is present.
  • public poll(): This method retrieves and removes the head of this queue, or returns null if this queue is empty.
  • public peek(): This method retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
  • void clear(): This method is used to remove all of the contents of the priority queue.
  • int size(): The method is used to return the number of elements present in the set.

Note: The above methods are applicable in case of both Max-Heap and Min-heap implementation of PriorityQueue class.

Implementation:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:
Some error occured or ide is down,please try again

Problem #1 : Heap Sort - Ascending Order

Description - Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.
Solution -Heap Sort Algorithm for sorting in increasing order-
  1. Build a max heap from the input data.
  2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
  3. Repeat above steps while size of heap is greater than 1.
Pseudo Code
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify( arr[], n, i)
{
largest = i // Initialize largest as root
l = 2*i + 1 // left = 2*i + 1
r = 2*i + 2 // right = 2*i + 2

// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l

// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r

// If largest is not root
if (largest != i)
{
swap(arr[i], arr[largest])

// Recursively heapify the affected sub-tree
heapify(arr, n, largest)
}
}

// main function to do heap sort
void heapSort( arr[], n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i)

// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
swap(arr[0], arr[i])

// call max heapify on the reduced heap
heapify(arr, i, 0)
}
}

Problem #2 : K’th Smallest/Largest Element in Unsorted Array

Description - Given an array and a number k where k is smaller than size of array, we need to find the k’th smallest element in the given array. It is given that all array elements are distinct.
Solution - The idea is create Min Heap and extract k elements from the element, kth extracted element will be the kth smallest element in the array.
Pseudo Code
void MinHeap( a[], size) 
{
heap_size = size
harr = a // store address of array
int i = (heap_size - 1)/2
while (i >= 0)
{
MinHeapify(i)
i--
}
}

// Method to remove minimum element (or root) from min heap
int extractMin()
{
if (heap_size == 0)
return INT_MAX

// Store the minimum vakue.
int root = harr[0]

// If there are more than 1 items, move the last item to root
// and call heapify.
if (heap_size > 1)
{
harr[0] = harr[heap_size-1]
MinHeapify(0)
}
heap_size--

return root
}
// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeapify(int i)
{
int l = left(i)
int r = right(i)
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l
if (r < heap_size && harr[r] < harr[smallest])
smallest = r
if (smallest != i)
{
swap(& harr[i], & harr[smallest])
MinHeapify(smallest)
}
}
// Returns Minimum Element
int getMin()
{
return harr[0]
}
// Function to return k'th smallest element in a given array
int kthSmallest( arr[], n, k)
{
// Build a heap of n elements: O(n) time
MinHeap(arr, n)

// Do extract min (k-1) times
for (int i=0; i < k-1; i++)
extractMin()

// Return root
return getMin()
}

Problem #3 : Median of Stream of Running Integers using STL

Description - Given that integers are being read from a data stream. Find median of all the elements read so far starting from the first integer till the last integer. This is also called Median of Running Integers. The data stream can be any source of data, example: a file, an array of integers, input stream etc.

What is Median?

Median can be defined as the element in the data set which separates the higher half of the data sample from the lower half. In other words we can get the median element as, when the input size is odd, we take the middle element of sorted data. If the input size is even, we pick average of middle two elements in sorted stream.
Example:
Input: 5 10 15
Output: 5
7.5
10
Explanation: Given the input stream as an array of integers [5,10,15]. We will now read integers one by one and print the median correspondingly. So, after reading first element 5, the median is 5. After reading 10,median is 7.5 After reading 15 ,median is 10.
Solution - The idea is to use max heap and min heap to store the elements of higher half and lower half. Max heap and min heap can be implemented using priority_queue in C++ STL. Below is the step by step algorithm to solve this problem.
  1. Create two heaps. One max heap to maintain elements of lower half and one min heap to maintain elements of higher half at any point of time..
  2. Take initial value of median as 0.
  3. For every newly read element, insert it into either max heap or min heap and calulate the median based on the following conditions:
    • If the size of max heap is greater than size of min heap and the element is less than previous median then pop the top element from max heap and insert into min heap and insert the new element to max heap else insert the new element to min heap. Calculate the new median as average of top of elements of both max and min heap.
    • If the size of max heap is less than size of min heap and the element is greater than previous median then pop the top element from min heap and insert into max heap and insert the new element to min heap else insert the new element to max heap. Calculate the new median as average of top of elements of both max and min heap.
    • If the size of both heaps are same. Then check if current is less than previous median or not. If the current element is less than previous median then insert it to max heap and new median will be equal to top element of max heap. If the current element is greater than previous median then insert it to min heap and new median will be equal to top element of min heap.
Pseudo Code
// function to calculate median of stream
void printMedian(double arr[], int n)
{
// max heap to store the smaller half elements
priority_queue s;

// min heap to store the greater half elements
priority_queue,greater > g;

double med = arr[0];
s.push(arr[0]);

print(med)

// reading elements of stream one by one
/* At any time we try to make heaps balanced and
their sizes differ by at-most 1. If heaps are
balanced,then we declare median as average of
min_heap_right.top() and max_heap_left.top()
If heaps are unbalanced,then median is defined
as the top element of heap of larger size */
for (int i=1; i < n; i++)
{
double x = arr[i];

// case1(left side heap has more elements)
if (s.size() > g.size())
{
if (x < med)
{
g.push(s.top());
s.pop();
s.push(x);
}
else
g.push(x);

med = (s.top() + g.top())/2.0;
}

// case2(both heaps are balanced)
else if (s.size()==g.size())
{
if (x < med)
{
s.push(x);
med = (double)s.top();
}
else
{
g.push(x);
med = (double)g.top();
}
}

// case3(right side heap has more elements)
else
{
if (x > med)
{
s.push(g.top());
g.pop();
g.push(x);
}
else
s.push(x);

med = (s.top() + g.top())/2.0;
}

print(med)
}
}
Time Complexity: O(n Log n)
Auxiliary Space : O(n)

Nearly sorted

Asked In: Amazon

Question 1 [1 Marks]
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?
A
1, 3, 5, 6, 8, 9
B
9, 6, 3, 1, 8, 5
C
9, 3, 6, 8, 5, 1
D
9, 5, 6, 8, 3, 1
Explanation

If you are facing any issue on this page. Please let us know.